#include <iostream>
#include <vector>

/**
 * @brief 结构体 Fragment 包括报文长度和偏移量。 
 */
struct Fragment {
    int length;
    int offset;
};

/**
 * @brief 输入报文长度（报文头固定占 20 字节），和传输路径上所有网络的 MTU，输出报文分片的结果。
 * 
 * @param packetLength 报文长度
 * @param pathMTUs 传输路径上所有网络的 MTU
 * @return std::vector<Fragment> 报文分片的结果
 */
std::vector<Fragment> fragmentPacket(int packetLength, const std::vector<int>& pathMTUs)
{
    std::vector<Fragment> fragments;
    fragments.push_back(Fragment{packetLength, 0});

    for (auto MTU : pathMTUs)
    {
        for (int i = 0; i < fragments.size(); i++)
        {
            Fragment fragment = fragments[i];
            if (fragment.length > MTU)
            {
                int maxOffset = (MTU - 20) / 8;
                int maxDataLength = maxOffset * 8;
                int maxFragmentLength = maxDataLength + 20;
                int count = (fragment.length - 20) / maxDataLength; // 计算能够分出最大的片的个数
                int leftover = (fragment.length - 20) % maxDataLength; // 计算剩下的字节数

                for (int j = 0; j < count; j++)
                    fragments.insert(fragments.begin() + i + j + 1, Fragment{maxFragmentLength, fragment.offset + j * maxOffset});
                
                if (leftover > 0)
                    fragments.insert(fragments.begin() + i + count + 1, Fragment{leftover + 20, fragment.offset + count * maxOffset});

                fragments.erase(fragments.begin() + i);
                
                // 更新偏移量
                i += count - 1;
                if (leftover > 0) i++;
            }
        }    
    }

    return fragments;
}

int main()
{
    int packetLength = 24000;
    std::vector<int> pathMTUs = {4325, 2346, 1500, 4464, 2346};

    std::vector<Fragment> fragments = fragmentPacket(packetLength, pathMTUs);

    std::cout << "Fragmentation result:" << std::endl;
    for (int i = 0; i < fragments.size(); i++)
        std::cout << "Fragment " << i + 1 << ": length = " << fragments[i].length << ", offset = " << fragments[i].offset << std::endl;
    
    return 0;
}